import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * 主要就是避免重复
 *暴力方法的话可以将符合要求的数组进行排序，然后放入list和set，list是用来返回数据的
 * set用来避免重复的，我们将list排序后转为string，判断set里面是否含有当前的数组，存在就不将当前list不存入结果集
 * 不存在就加入结果集
 */
public class _15_三数之和__二分查找解法 {
    @Test
    void test(){
        int []nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum1(nums));
    }


    //使用双指针，二分查找
    public List<List<Integer>> threeSum1(int[] nums) {

        if (nums.length<3||nums==null){
            return new ArrayList<>();
        }

        Set<List<Integer>> res = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 在 i + 1 ... nums.length - 1 中查找相加等于 -nums[i] 的两个数
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return new ArrayList<>(res); // O(n)
    }
}
